package com.le.basic.matrix;

/**
 * 在行列都排好序的矩阵中找数
 * 【题目】 给定一个有N*M的整型矩阵matrix和一个整数K， matrix的每一行和每一 列都是排好序的。
 * 实现一个函数，判断K 是否在matrix中。
 * 例如：
    *  0   1   2   5
    *  2   3   4   7
    *  4   4   4   8
    *  5   7   7   9
 * 如果K为7，返回true；如果K为6，返 回false。
 * 【要求】 时间复杂度为O(N+M)，额外空间复杂度为O(1)。
 */
public class Code_09_FindNumInSortedMatrix {

    /**
     * 解题思想: 定位到右上角点或者左下角点,进行判断
     * @param matrix
     * @param k
     * @return
     */
    private static boolean findNum(int[][] matrix, int k) {
        // 获取右上角点 行和列
        int r = 0;
        int c = matrix[0].length - 1;
        while (r < matrix.length && c > -1){
            if (matrix[r][c] == k){
                return true;
            }else if (matrix[r][c] > k){
                c--;
            }else {
                r++;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] matrix = {
                {0, 1, 2, 5},//[0,3]
                {2, 3, 4, 7},
                {4, 4, 4, 8},
                {5, 7, 7, 9}//[3,3]
        };
        boolean flag = findNum(matrix,6);
        System.out.println(flag);
    }
}
